A Binary Search Tree is a special Binary tree (each parent node can have maximum 2 node), which satisfy the following condition.
- The tree must be a binary search tree.
- The left sub-tree key value should be less than the parent node key value.
- The right-sub tree key value should be greater than the parent node key value.
If a tree satisfies the above 3 conditions then it would be considered as a Binary Search Tree.
Binary Search Tree Representation
Let’s represent a binary search tree which keys values are [31,16,61,8,23,46,77,19,28]
31 / \ / \ 16 61 / \ / \ 8 23 46 77 / \ 19 29
The binary tree is a Binary Search tree because each node has 2 or less than 2 child nodes, and each parent node left child is smaller than the parent node and the right child is greater than the parent node.
Advantages of Binary Search Tree
- It optimizes the searching algorithm, as we know that the elements on the right side are greater than the parent node and elements on the left side are smaller than the parent node so, with simple comparison, we can search any element efficiently.
- The insertion of the new element in a binary search tree is also very easy.
- If we compare it with the linked list and array it is more efficient.
Complexities
| Algorithms | Average Complexity | Worst Complexity |
| Space | O(n) | O(n) |
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
Basic Operations on Binary Search Tree
Like other data structure we can perform some basic operations on Binary Search Tree:
- Insertion
- Deletion
- Traversal
- Searching
Insertion
In BST the insertion takes place always at the bottom of a tree. No matter what the new element inserted in the tree become the leaf node of the tree. Suppose we have a tree:
31 / \ / \ 16 61
Insert
100 is greater than root node 31 so it lay on the right subtree of the tree. But 31 already has a right child 61, so now we will compare the right child of the parent node with the new element 100.
31 / \ / \ 16 61
The right subtree has already a node 61 so we will compare 100 with 61, and 100 is greater than 61 so it resides as the right child of 61 because 61 does not have any child.
31 / \ / \ 16 61 \ 100
Insertion algorithm
def insert(key,data,currentnode): if not root: root = Node(key,data) else: if key < root.key: if currentnode.hasLeftChild(): insert(key,data,currentnode.leftchild) else: currentnode.leftChild = Node(key,data) else: if currentnode.hasLeftChild(): insert(key,data,currentnode.leftchild) else: currentnode.leftChild = Node(key,data)
Deletion
Deletion is the most complex and lengthy operation of BST, when we perform the deletion operation, we have to take care of three conditions.
- The node we have to delete is a leaf node
- The node we have to delete has only one child.
- The node we have to delete has 2 child nodes.
Traversal
Like a binary tree, we can use any of the tree traversal methods on BST to visits each node. Those three methods are
- Pre-Order Traversal
- In-Order Traversal
- Post-Order Traversal.
Searching
To retrieve the data of any particular node we can perform the search operation on the Binary search tree. To search the data, we use the corresponding key value.
Implementation of Binary Search Tree
In Python
Here we will use python to implement a Binary Search Tree. We use the class to create the structure for binary search tree and use node to create specific nodes that will reside in the BST.
class Node:
def __init__(self,key,val,left=None,right=None,parent=None):
self.key = key
self.data = val
self.leftChild = left
self.rightChild = right
self.parent = parent
def hasLeftChild(self):
return self.leftChild
def hasRightChild(self):
return self.rightChild
def isLeftChild(self):
return self.parent and self.parent.leftChild == self
def isRightChild(self):
return self.parent and self.parent.rightChild == self
def isRoot(self):
return not self.parent
def isLeaf(self):
return not (self.rightChild or self.leftChild)
def hasAnyChildren(self):
return self.rightChild or self.leftChild
def hasBothChildren(self):
return self.rightChild and self.leftChild
def replaceNodeData(self,key,value,lc,rc):
self.key = key
self.data = value
self.leftChild = lc
self.rightChild = rc
if self.hasLeftChild():
self.leftChild.parent = self
if self.hasRightChild():
self.rightChild.parent = self
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def length(self):
return self.size
def __len__(self):
return self.size
def insert(self,key,val):
if self.root:
self._insert(key,val,self.root)
else:
self.root = Node(key,val)
self.size = self.size + 1
def _insert(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._insert(key,val,currentNode.leftChild)
else:
currentNode.leftChild = Node(key,val,parent=currentNode)
else:
if currentNode.hasRightChild():
self._insert(key,val,currentNode.rightChild)
else:
currentNode.rightChild = Node(key,val,parent=currentNode)
def __setitem__(self,k,v):
self.insert(k,v)
def search(self,key):
if self.root:
res = self._search(key,self.root)
if res:
return res.data
else:
return None
else:
return None
def _search(self,key,currentNode):
if not currentNode:
return None
elif currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._search(key,currentNode.leftChild)
else:
return self._search(key,currentNode.rightChild)
def __searchitem__(self,key):
return self.search(key)
def __contains__(self,key):
if self._search(key,self.root):
return True
else:
return False
def delete(self,key):
if self.size > 1:
nodeToRemove = self._search(key,self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size = self.size-1
else:
raise KeyError('Error, key not in tree')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size = self.size - 1
else:
raise KeyError('Error, key not in tree')
def __delitem__(self,key):
self.delete(key)
def spliceOut(self):
if self.isLeaf():
if self.isLeftChild():
self.parent.leftChild = None
else:
self.parent.rightChild = None
elif self.hasAnyChildren():
if self.hasLeftChild():
if self.isLeftChild():
self.parent.leftChild = self.leftChild
else:
self.parent.rightChild = self.leftChild
self.leftChild.parent = self.parent
else:
if self.isLeftChild():
self.parent.leftChild = self.rightChild
else:
self.parent.rightChild = self.rightChild
self.rightChild.parent = self.parent
def findSuccessor(self):
succ = None
if self.hasRightChild():
succ = self.rightChild.findMin()
else:
if self.parent:
if self.isLeftChild():
succ = self.parent
else:
self.parent.rightChild = None
succ = self.parent.findSuccessor()
self.parent.rightChild = self
return succ
def findMin(self):
current = self
while current.hasLeftChild():
current = current.leftChild
return current
def remove(self,currentNode):
if currentNode.isLeaf(): #leaf
if currentNode == currentNode.parent.leftChild:
currentNode.parent.leftChild = None
else:
currentNode.parent.rightChild = None
elif currentNode.hasBothChildren(): #interior
succ = currentNode.findSuccessor()
succ.spliceOut()
currentNode.key = succ.key
currentNode.data = succ.data
else: # this node has one child
if currentNode.hasLeftChild():
if currentNode.isLeftChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.leftChild
elif currentNode.isRightChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.leftChild
else:
currentNode.replaceNodeData(currentNode.leftChild.key,
currentNode.leftChild.data,
currentNode.leftChild.leftChild,
currentNode.leftChild.rightChild)
else:
if currentNode.isLeftChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.rightChild
elif currentNode.isRightChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.rightChild
else:
currentNode.replaceNodeData(currentNode.rightChild.key,
currentNode.rightChild.data,
currentNode.rightChild.leftChild,
currentNode.rightChild.rightChild)
People are also reading: